/*
* 问题归类为：nSum
* 核心思路：排序 + 双指针
*
*
*
*
*
* */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_1 {
    public List<List<Integer>> threeSum(int[] nums) {
        //对数组先进行排序
        Arrays.sort(nums);

        //创建结果列表
        List<List<Integer>> result = new ArrayList<>();

        //获取数组长度
        int length = nums.length;

        //开始双指针算法
        //for循环后面要留两个指针位，所以 k 最大倒 length - 3
        for(int k=0;k<length-2;k++)
        {
            //因为已排序，所以第一个加数如果大于0，直接跳出
            if(nums[k]>0) break;

            //当前数和前一个数相同，则跳过，避免重复
            if(k>0&&nums[k]==nums[k-1]) continue;

            //初始化另外两个索引
            int i=k+1,j=length-1;
            while (i<j)
            {
                //三数之和
                int sum=nums[k]+nums[i]+nums[j];
                if(sum<0)
                {
                    //避免数相等
                    while(i < j && nums[i] == nums[++i]);
                }
                else if (sum>0)
                {
                    while(i < j && nums[j] == nums[--j]);
                }
                else {
                    result.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }

        return result;
    }
}
